// 线段交叉
import { _k } from '../math/index.js'
import { triArea } from './area.js'
// import { plainMatrix } from '../math/index.js'

// 四个点的交叉点
// 算法三: 判断每一条线段的两个端点是否都在另一条线段的两侧, 是则求出两条线段所在直线的交点, 否则不相交.
// 不通过法线投影来判断点和线段的位置关系, 而是通过点和线段构成的三角形面积来判断.
// 如果”线段ab和点c构成的三角形面积”与”线段ab和点d构成的三角形面积” 构成的三角形面积的正负符号相异,
// 那么点c和点d位于线段ab两侧.
export const segmentsIntr = ([a, b], [c, d]) => {

    // 三角形abc 面积
    var area_abc = triArea(a, b, c)  //(a[0] - c[0]) * (b[1] - c[1]) - (a[1] - c[1]) * (b[0] - c[0]);

    // 三角形abd 面积
    var area_abd = triArea(a, b, d)  //(a[0] - d[0]) * (b[1] - d[1]) - (a[1] - d[1]) * (b[0] - d[0]);

    // 面积符号相同则两点在线段同侧,不相交 (对点在线段上的情况,本例当作不相交处理); 
    if (area_abc * area_abd >= 0) {
        return false;
    }

    // 三角形cda 面积
    var area_cda = triArea(c, d, a)  //(c[0] - a[0]) * (d[1] - a[1]) - (c[1] - a[1]) * (d[0] - a[0]);
    // 三角形cdb 面积的2倍 
    // 注意: 这里有一个小优化.不需要再用公式计算面积,而是通过已知的三个面积加减得出. 
    var area_cdb = area_cda + area_abc - area_abd;
    if (area_cda * area_cdb >= 0) {
        return false;
    }

    //计算交点坐标 
    var t = area_cda / (area_abd - area_abc);
    var dx = t * (b[0] - a[0]),
        dy = t * (b[1] - a[1]);
    return [_k(a[0] + dx), _k(a[1] + dy)];
}


// 边与线段 交点 
export const edgeCrossPoints = (points, segs) => {
    let lcps = []
    let n = segs.length
    let m = points.length
    for (let i = 0; i < n ; i++) {
        let seg = segs[i]
        for (let j = 0; j < m; j++) {
            let t = points[j]
            let next = points[(j + 1) % m]
            let p = segmentsIntr(seg, [t, next])
            if (p) {
                lcps.push(p)
            }
        }
    }
    return lcps

}

// 线段的所有交点
export const segCrossPoints = (segs) => {
    let ps = []
    let len = segs.length
    for (let i = 0; i < len; i++) {
        let seg = segs[i]
        for (let j = i + 1; j < len; j++) {
            let next = segs[j]
            let p = segmentsIntr(seg, next)
            if (p) {
                ps.push(p)
            }
        }
    }
    return ps
}

// links seg Matrix
// export const segCrossPoints = (segs) => {
//     let lcps = []
//     for (let i = 0; i < segs.length - 1; i++) {
//         let seg = segs[i]
//         let others = segs.slice(i + 1)
//         let osegs = plainMatrix(others)
//         seg.forEach(u => {
//             osegs.forEach(v => {
//                 let p = segmentsIntr(u, v)
//                 if (p) {
//                     lcps.push(p)
//                 }
//             })
//         })
//     }
//     return lcps
// }

// 隔壁线段的 交点
export const neighbourSegCrossPoints = (segs) => {
    let lcps = []
    let len = segs.length
    for (let i = 0; i < len; i++) {
        let seg = segs[i]
        let next = segs[(i + 1) % len]
        let p = segmentsIntr(seg, next)
        if (p) {
            lcps.push(p)
        }
    }
    return lcps

}